package _04;

import java.util.Scanner;

/**
 * @author ：Rwto
 * @date ：Created in 2021/7/11 22:25
 * @description：二维数组的查找 时间复杂度O(n+m)
 */
public class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0)
            return false;
        int m = matrix.length; //行数
        int n = matrix[0].length; //列数
        //从右上角开始
        int row=0;
        int col=n-1;
        while(row<m&&col>=0){
            if(matrix[row][col]>target){
                col--;
            }else if(matrix[row][col]<target){
                row++;
            }else{
                return true;
            }
        }
        return false;
    }

    public static void  main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("输入行和列");
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] matrix = new int[n][m];
        System.out.println("输入二维数组");

        for(int i = 0 ;i<n ;i++){
            for(int  j = 0; j<m ; j++){
                int tmp = sc.nextInt();
                matrix[i][j] = tmp;
            }
        }
        System.out.println("输入目标数");
        while(sc.hasNext()){
            int target = sc.nextInt();
            System.out.println(new Solution().findNumberIn2DArray(matrix,target));
        }
    }
}